/**
 * @program: LeetCode
 * @description: LeetCode : 面试题 17.16. 按摩师
 * @author: WXY
 * @create: 2023-01-05 20:31
 * @Version 1.0
 **/
public class Num17_16_massage {
    public static int massage1(int[] arr) {
        int res = process(arr, 0, 0);
        return res;
    }


    //i ... 及其往后的选择
    private static int process(int[] arr, int i, int ans) {
        if (i == arr.length) {
            return ans;
        }
        int yes = 0;
        if (i == arr.length - 1) {
            yes = ans + arr[i];
        } else {
            yes = process(arr, i + 2, ans + arr[i]);
        }
        int no = process(arr, i + 1, ans);
        int res = Math.max(no, yes);
        return res;
    }

    public static int massage(int[] arr) {
        if (arr.length == 0) return 0;
        if (arr.length == 1) return arr[0];
        int[] dp = new int[arr.length + 1];
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0], arr[1]);
        for (int i = 2; i < arr.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i]);
        }
        return dp[arr.length - 1];
    }


    public static void main(String[] args) {
        int[] arr = {1, 9, 2, 4, 7};
        int massage = massage(arr);
        System.out.println(massage);
    }
}
